package com.lcm.oj.lanqiao.year2021.moni.demo;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Coder-lcm
 * @date 2021/4/17
 *
 *  回溯算法求全排列（无重复元素）
 */
public class QuanPaiLie {
    static List<List<Integer>> res = new ArrayList<>();
    // 已经走过的路径
    static LinkedList<Integer> route = new LinkedList<>();

    public static void backTrack(int[] nums, LinkedList<Integer> route) {
        // 递归结束标志
        if (route.size() == nums.length) {
            res.add(new LinkedList(route));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 该节点已走过
            if (route.contains(nums[i])) {
                continue;
            }
            route.add(nums[i]);
            // 回溯
            backTrack(nums, route);
            // 回溯完撤销选择
            route.removeLast();
        }
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5};
        backTrack(nums, route);
        res.forEach(each -> {
            each.forEach(e -> {
                System.out.print(e + " ");
            });
            System.out.println();
        });
    }
}
